package hermesV3.services.Space;

import it.unicam.cs.cosy.bioshape.core.components.ProtoEntity;
import it.unicam.cs.cosy.bioshape.core.components.exception.NotEnoughSpaceException;

import java.util.ArrayList;
import java.util.Hashtable;

import javax.vecmath.Point3d;
import javax.vecmath.Vector3d;

/**
 * Implements a simple algorithm for entities placement in the given simulation
 * space on the basis of an {@link OctreeNode} data structure.
 * 
 * @author Alanis Gaston, Matteo Micheletti, Andrea Piermarteri, Federico Buti
 */
// TODO rotation version must be revisited
public class Placement {

	private Point3d[] bounds = new Point3d[2];
	private double spaceVolume;
	private ArrayList<ArrayList<ProtoEntity>> matrix;
	private Hashtable<Point3d, Integer> leaves;

	/**
	 * Builds a placement object with the passed volume bounds and volume
	 * 
	 * @param bounds
	 *            the bounds of the volume in which execute the placement
	 * @param spaceVolume
	 *            the overall volume of the space in which execute the placement
	 */
	public Placement(Point3d[] bounds, double spaceVolume) {
		this.bounds = bounds;
		this.spaceVolume = spaceVolume;
	}

	/**
	 * Fills a matrix with the EntityDatas, arranging them into it, by volume
	 * size.<br>
	 * For each column of the matrix is defined a maximal volume size that can
	 * be contained in it. Only BBs with volume lower or equal to the volume
	 * defined in a column, can be inserted in the specific column.<br>
	 * If a volume cannot be placed, then there is not enough space in the
	 * overall volume and an exception is thrown.<br>
	 * 
	 * @see it.unicam.cs.cosy.bioshape.core.components.EntityData
	 * 
	 * @param dataList
	 *            object list.
	 * @return a matrix containing the arranged EntityDatas
	 * 
	 * @throws NotEnoughSpaceException
	 *             if the BB dimensions are greater than the sub-volume
	 *             dimensions or if the sum of all the BB volumes is greater
	 *             than the total space volume.
	 */
	private ArrayList<ArrayList<ProtoEntity>> fillMatrixWithoutRotation(
			ArrayList<ProtoEntity> dataList) throws NotEnoughSpaceException {
		ArrayList<ArrayList<ProtoEntity>> dataMatrix = new ArrayList<ArrayList<ProtoEntity>>();
		// difference between simulation space bounds
		Point3d bound0 = new Point3d(bounds[0].getX(), bounds[0].getY(),
				bounds[0].getZ());
		Point3d spaceSize = new Point3d(bounds[1].getX(), bounds[1].getY(),
				bounds[1].getZ());
		spaceSize.sub(bound0);
		// partial volume occupied by entities already placed
		double sum = 0;
		for (ProtoEntity eData : dataList) {
			int card = eData.getCardinality();
			while (card-- > 0) {
				Point3d bounds = eData.getBB();
				boolean placed = false;
				int level = 0;
				while (eData.getBBVolume() <= (spaceVolume / Math.pow(8.0,
						level)))
					level++;
				level--; // level which can surely contain the EntityData...
				// add levels if needed --> save memory
				while (dataMatrix.size() <= level)
					dataMatrix.add(new ArrayList<ProtoEntity>());
				// adding the EntityData to the level that contains all
				// coordinates
				// iff the maximal volume is NOT exceeded
				while (level >= 0 && !placed) {
					if (bounds.x <= (spaceSize.x / Math.pow(2.0, level))
							&& bounds.y <= (spaceSize.y / Math.pow(2.0, level))
							&& bounds.z <= (spaceSize.z / Math.pow(2.0, level))) {
						if ((sum += 1.0 / Math.pow(8.0, level)) > 1.0)
							throw new NotEnoughSpaceException();
						dataMatrix.get(level).add(eData);
						placed = true;
					} else
						level--;
				}
				//
				if (!placed)
					throw new NotEnoughSpaceException();
			}
		}
		return dataMatrix;
	}

	/**
	 * Fills a matrix with the EntityDatas, arranging them into it by size.<br>
	 * For each column is defined the maximum size the BB must be for being
	 * inserted into that column. However, the BB dimensions must be lower or
	 * equal than the sub-volume dimensions; if they are not, the BB is rotated
	 * trying to find a way to fit it into the sub-volume.<br>
	 * If the sum of all the BB volumes is greater than the total space volume,
	 * it is impossible to place all the BB into the space and an exception is
	 * thrown.
	 * 
	 * @see it.unicam.cs.cosy.bioshape.core.components.EntityData
	 * 
	 * @param dataList
	 *            object list.
	 * @return a matrix containing the arranged EntityDatas
	 * 
	 * @throws NotEnoughSpaceException
	 *             If the sum of all the BB volumes is greater than the total
	 *             space volume
	 * 
	 *             private ArrayList<ArrayList<ProtoEntity>> fillMatrix(
	 *             ArrayList<ProtoEntity> dataList) throws
	 *             NotEnoughSpaceException { ArrayList<ArrayList<ProtoEntity>>
	 *             dataMatrix = new ArrayList<ArrayList<ProtoEntity>>(); int j;
	 *             double sum = 0; boolean placed = false; // for (ProtoEntity
	 *             eData : dataList) { int card = eData.getCardinality(); // add
	 *             as many times as the numer of real entities to be created
	 *             while (card-- > 0) { placed = false; j = 0; while
	 *             (eData.getBBVolume() <= (spaceVolume / Math.pow(8.0, j)))
	 *             j++; j--; // add levels to the matrix if necessary... while
	 *             (dataMatrix.size() <= j) dataMatrix.add(new
	 *             ArrayList<ProtoEntity>()); // BB fits in the j-level
	 *             subvolume... int level = j; Vector3d orientation; while
	 *             (level >= 0 && placed == false) { // check all of the three
	 *             dimensions, if they fit, even // rotated; if not moves to an
	 *             higher level orientation = checkFilling(eData.getBB(),
	 *             level); if (orientation != null) { sum += 1.0 / Math.pow(8.0,
	 *             level); if (sum <= 1.0) { dataMatrix.get(level).add(eData);
	 *             placed = true; eData.setOrientations(orientation); } else
	 *             throw new NotEnoughSpaceException(); } else level--; } if
	 *             (!placed) throw new NotEnoughSpaceException(); } } return
	 *             dataMatrix; }
	 */

	/**
	 * Checks if it is possible to place a certain Bounding volume into an
	 * octree node at the octree level as input. If it is not possible, it tries
	 * to rotate the volume to fit in different positions.
	 * 
	 * @param shape
	 *            a Bounding Box
	 * @param level
	 *            the octree level
	 * @return the degrees of rotation (if necessary) to place the bounding
	 *         volume or {@code null} if it is not possible to position the
	 *         volume at the given level.
	 */
	@SuppressWarnings("unused")
	private Vector3d checkFilling(Point3d shape, int level) {

		Point3d bound0 = new Point3d(bounds[0].getX(), bounds[0].getY(),
				bounds[0].getZ());
		Point3d space = new Point3d(bounds[1].getX(), bounds[1].getY(),
				bounds[1].getZ());
		space.sub(bound0);

		space.setX(space.x / Math.pow(2.0, level));
		space.setY(space.y / Math.pow(2.0, level));
		space.setZ(space.z / Math.pow(2.0, level));

		if (shape.x <= space.x && shape.y <= space.y && shape.z <= space.z)
			return new Vector3d();
		// otherwise try to rotate it
		double[] spaceDim = sortDescending(space);
		double[] shapeDim = sortDescending(new Point3d(shape));
		//
		Vector3d rotation = new Vector3d();
		for (int i = 0; i < 3; i++) {
			if (shapeDim[i] > spaceDim[i])
				break;
			// faccio l'xor tra le rotazioni secondo gli scambi nella shape
			// e secondo gli scambi nello
			// space, per trovare le rotazioni effettive necessarie
			if (i == 0)
				rotation.x = ((int) spaceDim[i + 3] ^ (int) shapeDim[i + 3]) * 90;
			if (i == 1)
				rotation.y = ((int) spaceDim[i + 3] ^ (int) shapeDim[i + 3]) * 90;
			if (i == 2) {
				rotation.z = ((int) spaceDim[i + 3] ^ (int) shapeDim[i + 3]) * 90;
				return rotation;
			}
		}
		return null;
	}

	/**
	 * Sorts the input {@link Point3d} in ascending order by dimension.
	 * 
	 * 
	 * @param point
	 *            a {@link Point3d}
	 * @return the sorted {@link Point3d} points and the BoundingBox rotation
	 *         degrees
	 */
	private static double[] sortDescending(Point3d point) {
		double[] list = new double[] { point.getX(), point.getY(),
				point.getZ(), /* rotazione su asse x */0, /* rotazione su asse y */
				0, /* rotazione su asse z */0 };
		double temp;
		if (list[0] < list[1]) {
			temp = list[0];
			list[0] = list[1];
			list[1] = temp;
			// è necessaria una rotazione sull'asse z
			list[5] = 1;

		}
		if (list[1] < list[2]) {
			temp = list[1];
			list[1] = list[2];
			list[2] = temp;
			// è necessaria una rotazione sull'asse x
			list[3] = 1;
		}
		if (list[0] < list[1]) {
			temp = list[0];
			list[0] = list[1];
			list[1] = temp;
			// è necessaria una rotazione sull'asse z
			list[5] += 1;
		}
		if (list[3] == 1 && list[5] == 2) {
			// è sufficente una rotazione su y
			list[3] = 0;
			list[5] = 0;
			list[4] = 1;
		}
		//
		return list;
	}

	/**
	 * Builds the octree representing the placement of the EntityDatas given as
	 * input.
	 * 
	 * @see OctreeNode
	 * 
	 * @param matrix2
	 *            a list with the list of objects from the subdivision
	 * @return the filled octree root.
	 */
	private OctreeNode buildOctree(ArrayList<ArrayList<ProtoEntity>> matrix2) {
		OctreeNode root = null;
		// list of counters for every dimension
		ArrayList<Integer> amount = new ArrayList<Integer>();
		for (ArrayList<?> l : matrix2)
			amount.add(new Integer(l.size()));
		//
		double dim = 8;
		int i = -1;
		// search levels until the first NON empty is found
		while (++i < amount.size()) {
			dim /= 8;
			if (amount.get(i).intValue() != 0) {
				root = new OctreeNode(bounds[0], bounds[1], dim);
				// remove one index since we created the Octree
				Integer newValue = new Integer(amount.get(i).intValue() - 1);
				amount.set(i, newValue);
				break;
			}
		}
		// checks if "root" is null
		if (root == null)
			throw new RuntimeException();
		// ...if not, from that on we start placing other elements!
		while (i < amount.size()) {
			for (int j = 0; j < amount.get(i).intValue(); j++) {
				try {
					root.addElement(dim);
				} catch (NotEnoughSpaceException e) {
					e.printStackTrace();
				}
			}
			dim /= 8;
			i++;
		}
		return root;
	}

	/**
	 * Executes the placement of the entities without considering rotations.
	 * 
	 * @param list
	 *            list of entities to be positioned
	 * @param rotation
	 *            {@code true} if rotation must be considered during placement,
	 *            {@code false} otherwise. Rotations are currently <i>NOT</i>
	 *            supported.
	 * 
	 * @throws NotEnoughSpaceException
	 *             Thrown if the space available is not enough for the entities
	 *             to position
	 */
	public void place(ArrayList<ProtoEntity> list, boolean rotation)
			throws NotEnoughSpaceException {
		// matrix = rotation ? fillMatrix(list) :
		// fillMatrixWithoutRotation(list);
		matrix = fillMatrixWithoutRotation(list);
		OctreeNode root = buildOctree(matrix);
		// fill the hashtable with centers and leaf level
		leaves = root.getLeaves();
	}

	/**
	 * Assigns to each {@link ProtoEntity} its true center, a {@link Point3d}.<br>
	 * For each {@link ProtoEntity}, it checks if there is a center available at
	 * a certain level of division and assigns it. If the center is not
	 * available, it decreases the level of division until it finds an available
	 * one.
	 * 
	 * @return an ArrayList containing the {@link ProtoEntity}s with the centre
	 *         assigned.
	 */
	public ArrayList<ProtoEntity> setEntityCentres() {
		// create a structure where every list contains Points at the same level
		ArrayList<ProtoEntity> links = new ArrayList<ProtoEntity>();
		ArrayList<ArrayList<Point3d>> centres = new ArrayList<ArrayList<Point3d>>();
		for (int i = 0; i < matrix.size(); i++)
			centres.add(new ArrayList<Point3d>());
		// ...and populate it with ALL entities centers
		for (Point3d centre : leaves.keySet()) {
			int value = leaves.get(centre).intValue();
			centres.get(value).add(centre);
		}
		//
		// collection of indexes of centres for each placement level
		int[] indexes = new int[centres.size()];
		for (int i = 0; i < indexes.length; i++)
			if (centres.get(i).size() != 0)
				indexes[i] = centres.get(i).size() - 1;
		int level = 0;
		for (ArrayList<ProtoEntity> dataLevel : matrix)
			outer: for (ProtoEntity edata : dataLevel) {
				level = matrix.indexOf(dataLevel);
				// searches the "leaves" in the octree until it founds a level
				while (level >= 0) {
					if (leaves.containsValue(new Integer(level))) {
						Vector3d p = new Vector3d(centres.get(level).get(
								indexes[level]--));
						edata.addCenterAndRotation(p, null);
						links.add(edata);
						continue outer;
					}
					// otherwise looks for an higher level
					level--;
				}
			}
		return links;
	}
}